Two sum less than K

Time: O(NLogN); Space: O(1); easy

Given an array A of integers and integer K, return the maximum S such that there exists i smaller than j with A[i] + A[j] = S and S smaller than K. If no i, j exist satisfying this equation, return -1.

Example 1:

Input: A = [34,23,1,24,75,33,54,8], K = 60

Output: 58

Explanation:

  • We can use 34 and 24 to sum 58 which is less than 60.

Example 2:

Input: A = [10,20,30], K = 15

Output: -1

Explanation:

  • In this case it’s not possible to get a pair sum less that 15.

[1]:

class Solution1(object):
    def twoSumLessThanK(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        A.sort()
        result = -1
        left, right = 0, len(A)-1
        while left < right:
            if A[left]+A[right] >= K:
                right -= 1
            else:
                result = max(result, A[left]+A[right])
                left += 1
        return result

[2]:

s = Solution1()
A = [34,23,1,24,75,33,54,8]
K = 60
assert s.twoSumLessThanK(A, K) == 58
A = [10,20,30]
K = 15
assert s.twoSumLessThanK(A, K) == -1